class Node:
    def __init__(self, val):
        self.val = val
        self.neighbors = {}
        self.flag = -1


class Solution(object):
    def replaceWords(self, dictionary, sentence):
        """
        :type dictionary: List[str]
        :type sentence: str
        :rtype: str
        """
        dictionary.sort(key=lambda x: len(x))
        tree = Node('#')
        for index, word in enumerate(dictionary):
            node = tree
            for i in range(len(word)):
                if word[i] not in node.neighbors:
                    new_node = Node(word[i])
                    node.neighbors[word[i]] = new_node
                    node = new_node
                else:
                    node = node.neighbors[word[i]]
                    if node.flag >= 0:
                        break
            if node.flag < 0:
                node.flag = index

        out = []
        sentence = sentence.split(' ')
        for word in sentence:
            node = tree
            for i in range(len(word)):
                if word[i] in node.neighbors:
                    node = node.neighbors[word[i]]
                    if node.flag >= 0:
                        out.append(dictionary[node.flag])
                        break
                else:
                    break
            if node.flag < 0:
                out.append(word)
        return ' '.join(out)
